package com.academicsystem.www.utils;

import com.academicsystem.www.model.Edge;
import com.academicsystem.www.model.Vertex;
import lombok.experimental.UtilityClass;

import java.util.*;

/**
 * @author Jacky
 */
public class GraphUtils {
    public static void addVertex(Map<Integer,Vertex> vertexes,Integer lessonId){
        vertexes.put(lessonId,new Vertex(lessonId,null));
    }

    public static void addEdge(Map<Integer,Vertex> vertexes,Integer beginLessonId,Integer endLessonId) {
        // 获取出发顶点
        Vertex beginVertex = vertexes.get(beginLessonId);
        if(beginVertex == null) {
            // 没有开始顶点，创建
            beginVertex = new Vertex(beginLessonId,null);
            vertexes.put(beginLessonId,beginVertex);
        }
        // 创建边对象
        Edge edge = new Edge(endLessonId,null);
        if(beginVertex.getEdge() == null) {
            //当前顶点还没有边，直接设置
            beginVertex.setEdge(edge);
        }else {
            Edge lastEdge = beginVertex.getEdge();
            while(lastEdge.getNext() != null) {
                lastEdge = lastEdge.getNext();
            }
            // 设置到末尾
            lastEdge.setNext(edge);
        }
    }

    public static List<Integer> topologicalSort(Map<Integer,Vertex> vertexes) {
        //计算入度
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (Integer vertexId : vertexes.keySet()) {
            inDegree.put(vertexId, 0);
        }
        for (Vertex vertex : vertexes.values()) {
            Edge edge = vertex.getEdge();
            while (edge != null) {
                inDegree.put(edge.getLessonId(), inDegree.get(edge.getLessonId()) + 1);
                edge = edge.getNext();
            }
        }

        //将初始入度就为0的点放入队列
        Queue<Integer> queue = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        //排序好的列表
        List<Integer> sortedOrder = new ArrayList<>();

        //卡恩算法
        while (!queue.isEmpty()) {
            //将队列第一个点出队后放入列表
            Integer vertexId = queue.poll();
            sortedOrder.add(vertexId);

            //将与该元素相连的点的入度减一，若此时出现入度为0的点则入队
            Edge edge = vertexes.get(vertexId).getEdge();
            while (edge != null) {
                Integer endVertexId = edge.getLessonId();
                inDegree.put(endVertexId, inDegree.get(endVertexId) - 1);
                if (inDegree.get(endVertexId) == 0) {
                    queue.add(endVertexId);
                }
                edge = edge.getNext();
            }
        }

        //如果排序好的队列大小与点的个数不一则表示图中有循环，返回异常
        if (sortedOrder.size() != vertexes.size()) {
            throw new RuntimeException("Graph has a cycle, topological sort not possible");
        }

        return sortedOrder;
    }
}
